Networks typically provide multiple potential transmission paths from a source to a destination. For example, communication between a personal computer in Boston and a server in Los Angeles may be routed over a ten different (and equally reasonable) paths depending upon how the network is configured and the current traffic loading on each link among the intervening nodes. Routing on the Internet is typically done using a single path selected from among multiple available paths with the chosen path determined by various network administrators. The motivation behind such “ad hoc” routing is to simplify network management, reduce the need to update routing tables at the various nodes, etc., with the overall goal being more efficient network utilization.
Rather than selecting a single path for a communication session, some wired networks utilize multiple paths for a single session. For example, Asynchronous Transfer Mode (ATM) networks may quickly select among different paths to achieve responsive load balancing as well as to rapidly respond to network faults. In addition, the Open Shortest Path First (OSPF) protocol is intended to optimize multipath routing in Internet communications. However, the adaptation speed of OSPF is relatively low and OSPF is not generally used within a single TCP/IP (Transmission Control Protocol/Internet Protocol) stream.
Wireless ad hoc networks typically include a self-configuring array of nodes that combine RF (Radio Frequency) transceivers with processing capability and in some cases sensors. However, the expansion of ad hoc networks into vehicles and buildings introduces the problem of managing heterogeneous ad hoc networks with multipath routing where there are multiple administrative domains. Some of the problems introduced by this environment include the need to manage power consumption at each node, differing goals for performance optimization between the multiple administrative domains, and security concerns presented by un-trusted “men in the middle”.
Multipath routing algorithms have been proposed for optimizing performance in wireless ad hoc networks where each administrative domain may seek to optimize routing based on its own internal optimization goals but not necessarily in keeping with the optimization goals of other domains in the network. Networks managed in accordance with such schemes are commonly termed “selfish”.
However, such routing algorithms do not address the problem of malicious nodes in a network. In other words, routing algorithms typically assume all nodes in the network act in a “rational” manner and can be persuaded to forward network traffic if an appropriate incentive is provided. However, malicious nodes have different incentive structures that are non-rational in the context of the algorithm and are therefore not taken into account by typical routing algorithms. In light of the disclosure below, those skilled in the art will recognize that this problem is one form of the well-known “Byzantine Generals” problem.